The motion of flowing particles is often visualized and measured by recording a particle flow field with a standard or high speed camera. The recorded video is transferred to a computer, then particle images on the videos camera frames are recognized and their locations stored. From the stored locations of particle images on each camera frame, sequences of particle images through successive camera frames are automatically recognized as particle trajectories. The difficulty, complexity, and computer time required to automatically recognize particle trajectories increases exponentially with concentration of particles (number of particles per unit area on the camera frames).
A large number of different methods have been developed and successfully applied to automatically recognize the trajectories of particles in flow fields of low to moderate particle concentration. These techniques are often referred to as Particle Image Velocimetry (PIV) or Particle Tracking Velocimetry (PTV), based on how the particle images are exposed onto successive camera frames and how many frames the trajectories are recognized through (usually two frames for PIV and many more than two for PTV). Both camera/computer-hardware and image processing algorithms for particle flow measurements are being constantly improved upon in terms of accuracy, spatial and temporal resolution, and dynamic range.
In general, all these methods recognize particle trajectories by tracking some characteristic of particle images through a number of chronologically successive camera frames. One of the most commonly used methods, often referred to as Particle Image Velocimetry (PIV), recognizes a pair of images of the same particle over a short period of time. The pair of images may be on the same camera frame (by double exposure of a camera frame) or two consecutive frames. PIV is usually used to measure the motion of a gas or fluid by using particles that are aerodynamically small enough to follow the gas/fluid flow. Numerous methods have been developed to recognize these two-image PIV trajectories, including cross-correlation techniques. Another class of trajectory recognition methods identifies distinguishing features of particle images, such as shape, color, or brightness, and uses the distinguishing features to recognize the same particle through successive camera frames. Recognizing trajectories through multiple camera frames is often called PTV. Many trajectory recognition methods for PTV attempt to recognize particle trajectories by extrapolation techniques.
Most trajectory recognition methods work reasonably well if the concentration of particles in the particle flow field is low. With low particle concentrations, the particle concentration is not high enough to occlude optical access for the camera view or to block illumination. Also, with low particle concentrations, particle trajectories do not repeatedly cross each other and particle images do not repeatedly overlap. However, particle flows of high concentration present a number of problems not found in low concentrations: optical access is almost completely occluded, almost all particle trajectories cross other trajectories, a high percentage of particle images overlap (either on the same frame or across frames), and some particles are not illuminated because they are in the shadow of other particles.
Trajectory recognition becomes exponentially more difficult as particle concentration increases. For a specific particle, there may be numerous particle images in the next camera frame that may or may not correspond (i.e., be the next image created by the same specific particle). This is referred to as correspondence ambiguity, and it increases rapidly with particle concentration.
A common approach is to use priori knowledge of the particle flow behavior to limit the area searched in successive camera frames for particle images corresponding to a specific particle. Areas of successive camera frames are searched for the next instances of a particle along its trajectory by extrapolating particle motion from preceding frames. Limiting the areas searched in successive frames reduces the number of particle images in consideration, and thus the number of correspondence ambiguities.
If the temporal scope of the tracking is extended to three or more frames, the problem becomes a multidimensional assignment problem. For a search originating from a single particle, if N particles are found in each search area of subsequent frames, the number of searches in a subsequent frames grows as N to a power equal to the number of frames since the originating particle, or N(number of frames). Particle trajectories usually extend through at least four or five frames, but typically they extend through tens or even hundreds of frames. Additionally, with high concentration particle flows, several particle images may be found in each search area. As an example of the increasing correspondence ambiguity at high particle concentrations, if, for example, 2 particles are found in each search area, after 5 frames the number of particles included in search areas by frame 5 is 25 or 32. If N=3, after 10 frames, the number of particles in consideration by frame 5 is more than 50,000.
Problems such as these are known to be NP-complete, i.e., there is no efficient algorithm to compute their solution. See Nemhauser, et al. Integer and Combinatorial Optimization, John Wiley and Sons, Inc., New York (1999). However, approximate solutions can be found using greedy search techniques and other heuristics. See, e.g., Veenman et al, “Establishing motion correspondence using extended temporal scope.” Artificial Intelligence, 145(1-2):227.243. The complexity of the correspondence analysis significantly increases due to the extended temporal scope, and the combinatorial techniques become computationally expensive. On the other hand, these techniques are able to resolve crossing trajectories and find an optimal set of trajectories even in the presence of particle occlusions and losses of particle images due to other issues such as overlapping or shadowing.
In an algorithm generally termed Multiple Hypothesis Tracking (MHT), multi-target tracking is performed using a series of hypotheses, where each hypothesis generates a series of candidate trajectories. A candidate trajectory is defined to be a sequence of images that are assumed to originate from the same particle. Thus, each hypothesis predicts the location (e.g., in an image plane) of a set of expected particle locations, and these are compared with actual images detected in the next camera frame. Each subsequent “child” hypothesis represents one possible interpretation of the new set of measurements and together with its “parent” hypothesis, represents one possible interpretation of all past measurements. MHT may also attempt to allow for missing and false detections. Consequently, as the number of measurements increases, the hypothesis tree generated from each originating particle increases rapidly, and methods which attempt to optimize a solution globally, over all measurements, requires prohibitive computational resources. This is a fundamental consideration in particle trajectory recognition algorithms and can place a severe restraint on the concentration of particles to be tracked and the number of successive frames included in the global solution.
In particle trajectory recognition applications, methods exist to restrain the combinatorial explosion which results as the number of frames and the population density of particles increases. Equivalent sliding window algorithms have been developed, which match points using a limited temporal scope. Another common approach is to eliminate trajectories from the hypothesis tree through application of path coherence, and to discard trajectories whose orientation is incompatible with a dominant orientation of the surrounding vectors. Other approaches utilize a “track error” system, in which an error coefficient is established for a track based on the deviation of a particle position from that expected by the two succeeding particle positions in the track. The track is rejected as a reasonable possibility when the summation of the error coefficients for the track exceeds a threshold value.
The method disclosed herein addresses the inherent disadvantages of the foregoing methods by utilizing priori knowledge of particle flow behavior while limiting the size, location, and shape of search areas in successive frames based on applying limits to particle velocity and acceleration. Trajectory recognition is first attempted on all particle images in a video using very small search areas, and when a trajectory is recognized, the particle images in the trajectory are removed from further searches. After all particle images in a video have been searched using the smallest search areas, the search areas are increased slightly by slightly relaxing the limits on particle velocity and acceleration and again, the images of recognized trajectories are removed from consideration in future searches with larger search areas. The process of recognizing trajectories using gradually increasing search areas continues until the search area reaches a size that exceeds a size corresponding to the maximum particle velocity or the size of the field-of-view. This iterative process, starting with the most severe restrictions on size and shape, recognizes the slowest, least accelerating particles first. This greatly reduces the difficulty and computational requirements of particle trajectory recognition, by initially recognizing the most problematic trajectories using uniquely defined search areas that are highly efficient at detecting such trajectories.
The approach of varying search areas based on limiting particle flow parameters is combined with other techniques, such as the use of imaginary images to compensate for lost images. The disclosure thus provides a highly efficient and accurate method for numerous real particle flow fields of research and industrial importance.